package com.example.demo;

import java.util.*;

/**
 * @author libo
 * @ClassName Test
 * @Description: TODO（这里用一句话描述这个类的作用)
 * @date 2019/2/25 18:33
 */
public class Test {
    public static void main(String[] args) {
       /*
        int  nums [] = {2, 7, 9,11, 15};
        int target = 9;
        for (int i =0; i< 10000000; i++){
            new Test().twoSum2(nums,target);
        }
        */
        ListNode node1 = new ListNode(9);
       // node1.next = new ListNode(4);
        //node1.next.next = new ListNode(3);

        ListNode node2 = new ListNode(1);
        node2.next = new ListNode(9);
        node2.next.next = new ListNode(9);
        node2.next.next.next = new ListNode(9);
        node2.next.next.next.next = new ListNode(9);
        long start = System.currentTimeMillis();
        ListNode addNode = addTwoNumbers(node1, node2);
        System.out.println(System.currentTimeMillis()-start);
    }

    public   int[] twoSum(int[] nums, int target) {
        int [] reArray = new int[2];
        for(int i = 0; i< nums.length; i++){
            for(int j = i+1; j <nums.length-1;j++){
                if(nums[i]+nums[j] == target){
                    reArray[0] = i;
                    reArray[1] = j;
                }
            }
        }
        return reArray;
    }

    public   int[] twoSum2(int[] nums, int target) {
        int [] reArray = new int[2];
        Integer [] copyArray = new Integer [nums.length] ;
        for (int i = 0; i < nums.length; i++) {
            copyArray[i] = nums[i];
        }
        /*List<Integer> list = new ArrayList<Integer>(nums.length);
        Collections.addAll(list,nums);*/
        List<Integer> list = Arrays.asList(copyArray);
        for(int i = 0; i< list.size()-1; i++){
                if (list.get(i) + list.get(i+1) == target){
                    reArray[0] = i;
                    reArray[1] = i+1;
                }
        }
        return reArray;
    }

    public int[] twoSum3(int[] nums, int target) {
        Map<Integer, Integer> m = new HashMap<>();
        for(int i = 0; i<nums.length; i++){
            if(m.get(target-nums[i]) != null){
                return new int[]{m.get(target-nums[i]), i};
            }
            m.put(nums[i],i);
        }
        return new int[]{0,0};
    }
    public static  ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        if (l1 == null || l2 == null) {
            return null;
        }
        int l1Sum = l1.val;
        int l2Sum = l2.val;
        int count1 = 1, count2 = 1;
        while (l1.next != null) {
            l1Sum += l1.next.val * Math.pow(10, count1);
            count1++;
            l1 = l1.next ;
        }

        while (l2.next != null) {
            l2Sum += l2.next.val * Math.pow(10, count2);
            count2++;
            l2 = l2.next;
        }
        int sumn = l1Sum + l2Sum;
        String str = String.valueOf(sumn);
        char[] chars = str.toCharArray();
        ListNode node = new ListNode(Integer.valueOf(String.valueOf(chars[chars.length - 1])));
        ListNode  temp = node;
        for (int i = chars.length - 2; i >= 0; i--) {
            temp.next = new ListNode(Integer.valueOf(String.valueOf(chars[i])));
            temp = temp.next;
        }
        return node;
    }

    public static  ListNode addTwoNumbers2(ListNode l1, ListNode l2) {
        if (l1 == null || l2 == null) {
            return null;
        }
        int carry = 0;
        ListNode p, dummy = new ListNode(0);
        p = dummy;
        while (l1 != null || l2 != null || carry != 0) {
            if (l1 != null) {
                carry += l1.val;
                l1 = l1.next;
            }
            if (l2 != null) {
                carry += l2.val;
                l2 = l2.next;
            }
            p.next = new ListNode(carry%10);
            carry /= 10;
            p = p.next;
        }
        return dummy.next;
    }

    public static  ListNode addTwoNumbers3(ListNode l1, ListNode l2) {
        ListNode dummyHead = new ListNode(0);
        ListNode p = l1, q = l2, curr = dummyHead;
        int carry = 0;
        while (p != null || q != null) {
            int x = (p != null) ? p.val : 0;
            int y = (q != null) ? q.val : 0;
            int sum = carry + x + y;
            carry = sum / 10;
            curr.next = new ListNode(sum % 10);
            curr = curr.next;
            if (p != null) p = p.next;
            if (q != null) q = q.next;
        }
        if (carry > 0) {
            curr.next = new ListNode(carry);
        }
        return dummyHead.next;
    }
}

class ListNode {
    int val;
    ListNode next;

    public ListNode(int x) {
        val = x;
    }


}
